// 提交链接：https://leetcode.cn/problems/minimum-speed-to-arrive-on-time/description/
// lc1870. 准时到达的列车最小时速
// 完成日期：2024/10/2
// c++ 二分查找

class Solution {
public:
    double calculateTotalTime(vector<int>& dist, double speed) 
    {  
        double totalTime = 0.0;  
        int n = dist.size();  
        for (int i = 0; i < n - 1; ++i) 
        {  
            // 每趟列车之间的等待时间向上取整（因为列车只能在整点发车）  
            totalTime += ceil(static_cast<double>(dist[i]) / speed);  
        }  
        // 最后一趟列车不需要等待，直接计算行驶时间  
        totalTime += static_cast<double>(dist[n - 1]) / speed;  
        return totalTime;  
    }  

    int minSpeedOnTime(vector<int>& dist, double hour){
        int l = 1;  
        int r = 1e7;  
        int result = -1;  
    
        while (l <= r)
        {  
            int mid = l + (r - l) / 2;  
            double totalTime = calculateTotalTime(dist, mid);  
    
            if (totalTime <= hour) 
            {  
                result = mid;  
                r = mid - 1; 
            } 
            else
                l = mid + 1;  
        }
        return result;  
    } 
};